package com.hgx.algorithm.base.sort;

import com.hgx.algorithm.base.utils.ArraySortUtil;

/**
 * master公式：
 * 复杂度计算：T(N) = a*T(N/b)+O(N^d)
 * log(b,a) > d -> 复杂度为O(N^log(b,a))
 * log(b,a) = d -> 复杂度为O(N^d * logN)
 * log(b,a) < d -> 复杂度为O(N^d)
 *
 * 归并排序
 * 时间复杂度：O(N*logN)
 * 额外空间复杂度：O(N)
 * 稳定性：稳定
 */
public class MergeSort {

    public static void main(String[] args) {

        for (int i = 0; i < 5000; i++) {
            int[] arr = ArraySortUtil.generateRandomArray(20, 100);
            ArraySortUtil.print(arr);
            sort(arr);
            ArraySortUtil.print(arr);
        }
    }

    /**
     * 归并排序
     *
     * @param arr 需要排序数组
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    /**
     * 归并排序实现：切分
     *
     * @param arr   排序数组
     * @param left  左坐标
     * @param right 右坐标
     */
    private static void mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
//        int mid = (left + right) / 2;
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    /**
     * 归并排序实现：数组排序
     *
     * @param arr   排序数组
     * @param left  左坐标
     * @param mid   切分点
     * @param right 右坐标
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        //辅助数组
        int[] help = new int[right - left + 1];

        int i = 0;
        int p1 = left;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= right) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }

        for (int j = 0; j < help.length; j++) {
            arr[left + j] = help[j];
        }
    }
}
